{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Task Scheduler"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #hash-table #counting #sorting #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #哈希表 #计数 #排序 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: leastInterval"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #任务调度器"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个用字符数组 <code>tasks</code> 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间，CPU 可以完成一个任务，或者处于待命状态。</p>\n",
    "\n",
    "<p>然而，两个<strong> 相同种类</strong> 的任务之间必须有长度为整数<strong> </strong><code>n</code><strong> </strong>的冷却时间，因此至少有连续 <code>n</code> 个单位时间内 CPU 在执行不同的任务，或者在待命状态。</p>\n",
    "\n",
    "<p>你需要计算完成所有任务所需要的<strong> 最短时间</strong> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>tasks = [\"A\",\"A\",\"A\",\"B\",\"B\",\"B\"], n = 2\n",
    "<strong>输出：</strong>8\n",
    "<strong>解释：</strong>A -> B -> (待命) -> A -> B -> (待命) -> A -> B\n",
    "     在本示例中，两个相同类型任务之间必须间隔长度为 n = 2 的冷却时间，而执行一个任务只需要一个单位时间，所以中间出现了（待命）状态。 </pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>tasks = [\"A\",\"A\",\"A\",\"B\",\"B\",\"B\"], n = 0\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>在这种情况下，任何大小为 6 的排列都可以满足要求，因为 n = 0\n",
    "[\"A\",\"A\",\"A\",\"B\",\"B\",\"B\"]\n",
    "[\"A\",\"B\",\"A\",\"B\",\"A\",\"B\"]\n",
    "[\"B\",\"B\",\"B\",\"A\",\"A\",\"A\"]\n",
    "...\n",
    "诸如此类\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>tasks = [\"A\",\"A\",\"A\",\"A\",\"A\",\"A\",\"B\",\"C\",\"D\",\"E\",\"F\",\"G\"], n = 2\n",
    "<strong>输出：</strong>16\n",
    "<strong>解释：</strong>一种可能的解决方案是：\n",
    "     A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> (待命) -> (待命) -> A -> (待命) -> (待命) -> A\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= task.length <= 10<sup>4</sup></code></li>\n",
    "\t<li><code>tasks[i]</code> 是大写英文字母</li>\n",
    "\t<li><code>n</code> 的取值范围为 <code>[0, 100]</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [task-scheduler](https://leetcode.cn/problems/task-scheduler/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [task-scheduler](https://leetcode.cn/problems/task-scheduler/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"A\",\"A\",\"A\",\"B\",\"B\",\"B\"]\\n2', '[\"A\",\"A\",\"A\",\"B\",\"B\",\"B\"]\\n0', '[\"A\",\"A\",\"A\",\"A\",\"A\",\"A\",\"B\",\"C\",\"D\",\"E\",\"F\",\"G\"]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastInterval(self, tasks: List[str], n: int) -> int:\n",
    "        count_tasks = Counter(tasks)\n",
    "        all_slots = 0\n",
    "        h = []\n",
    "        # build a max-heap\n",
    "        for k,v in count_tasks.items():\n",
    "            heapq.heappush(h,[-v,k])\n",
    "        \n",
    "        # loop through the heap\n",
    "        while h:\n",
    "            # i is for counting which slot is going to be taken in current bucket\n",
    "            i = 0\n",
    "            # store the items needed to be counted the next loop\n",
    "            temp =[]\n",
    "            # n is the slots needed in this bucket\n",
    "            while i <= n:\n",
    "                # the total slot should be counted\n",
    "                all_slots += 1\n",
    "                # if h has items to be added into the bucket, it's good to add the item\n",
    "                if h:\n",
    "                    num,task = heapq.heappop(h)\n",
    "                    # the frequency should be substracted (freq is negative, so add 1)\n",
    "                    num += 1\n",
    "                    # if freq reach to 0, no need to add the item into temp for the next loop\n",
    "                    if num < 0:\n",
    "                        temp.append([num,task])\n",
    "                # when the current bucket is the last bucket, no need to continue loop\n",
    "                if not h and not temp: break\n",
    "                # the next slot to be filled then\n",
    "                i += 1\n",
    "            for freq_task in temp:\n",
    "                heapq.heappush(h,freq_task)\n",
    "                \n",
    "        return all_slots\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastInterval(self, tasks, n):\n",
    "        \"\"\"\n",
    "        :type tasks: List[str]\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        dic = {}\n",
    "        max_cur = 0\n",
    "        max_num = 0\n",
    "        for task in tasks:\n",
    "            if task in dic:\n",
    "                dic[task] += 1\n",
    "                if dic[task] > max_cur:\n",
    "                    max_cur = dic[task]\n",
    "                    max_num = 0\n",
    "                if dic[task] == max_cur:\n",
    "                    max_num += 1\n",
    "            else:\n",
    "                dic[task] = 1\n",
    "        if (max_cur - 1) * (n + 1) + max_num > len(tasks):\n",
    "            return (max_cur - 1) * (n + 1) + max_num\n",
    "        else:\n",
    "            return len(tasks)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastInterval(self, tasks, n):\n",
    "        \"\"\"\n",
    "        :type tasks: List[str]\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # if len(tasks) == 0:\n",
    "        #     return 0\n",
    "        # from collections import Counter\n",
    "        # d = dict(Counter(tasks))\n",
    "        # count = n+1\n",
    "        # res = 0\n",
    "        # while sum(d.values()) != 0:\n",
    "        #     count = n+1\n",
    "        #     for k,v in d.items():\n",
    "        #         if count != 0:\n",
    "        #             if v == 0:\n",
    "        #                 count -= 1\n",
    "        #             else:\n",
    "        #                 d[k] -= 1\n",
    "        #                 count -= 1\n",
    "        #             res += 1\n",
    "        #         else:\n",
    "        #             if v != 0:\n",
    "        #                 d[k] -= 1\n",
    "        #                 res += 1\n",
    "        #     res += count\n",
    "        # res -= count\n",
    "        # return res\n",
    "        \n",
    "        if len(tasks) == 0:\n",
    "            return 0\n",
    "        from collections import Counter\n",
    "        d = dict(Counter(tasks))\n",
    "        count = {}\n",
    "        for k in d.keys():\n",
    "            count[k] = 0\n",
    "        res = 0\n",
    "        while sum(d.values()) != 0:\n",
    "            bk = \"\"\n",
    "            bv = 0\n",
    "            for k,v in d.items():\n",
    "                if v > bv and count[k] == 0:\n",
    "                    bv = v\n",
    "                    bk = k                \n",
    "            for k,v in count.items():\n",
    "                if v != 0:\n",
    "                    count[k] -= 1\n",
    "            res += 1\n",
    "            if bk:\n",
    "                d[bk] -= 1  \n",
    "                count[bk] = n\n",
    "        return res\n",
    "                        \n",
    "                    \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def leastInterval(self, tasks, n):\n",
    "        \"\"\"\n",
    "        :type tasks: List[str]\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # 1 排序\n",
    "        # 2 分布到不同\n",
    "        maxFreq, maxFreqCount=0, 0\n",
    "        f = [0 for x in range(26)] \n",
    "        freq = deque(f, maxlen=26)\n",
    "        for taskone in tasks:\n",
    "            freq[ord(taskone) - ord('A')] += 1\n",
    "        # freq.reverse()  \n",
    "        for i in range(26):\n",
    "            if freq[i] > maxFreq:\n",
    "                maxFreq = freq[i]\n",
    "                maxFreqCount = 1\n",
    "            elif freq[i] == maxFreq:\n",
    "                maxFreqCount += 1\n",
    "        return max(len(tasks), (maxFreq - 1) * (n + 1) + maxFreqCount) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def leastInterval(self, tasks, n):\n",
    "        \"\"\"\n",
    "        :type tasks: List[str]\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        class Task(object):\n",
    "            \"\"\"\n",
    "                Task class to encapsulate notion of task\n",
    "            \"\"\"\n",
    "            def __init__(self, name, count):\n",
    "                self.name  = name       # name of task\n",
    "                self.count = -count     # number of instances\n",
    "                self.time  = -1         # time at which it last ran\n",
    "\n",
    "            def __repr__(self):\n",
    "                return self.name +':' +str(self.count)\n",
    "\n",
    "            def schedule(self, time):\n",
    "                self.time   = time      # task is scheduled, update time at which it last ran\n",
    "                self.count  += 1        # decrease count    \n",
    "\n",
    "            #def __cmp__(self, other):\n",
    "            #    cmp(self.count, other.count)\n",
    "\n",
    "            def __lt__(self, other):\n",
    "                # if two have same count, use the one with lexicographically smaller\n",
    "                return self.count < other.count or self.count == other.count and self.name < other.name\n",
    "        \n",
    "        if n == 0:\n",
    "            # if no cooling period, simply return as many tasks as there're\n",
    "            return len(tasks)\n",
    "\n",
    "\n",
    "\n",
    "        task_collection = collections.Counter(tasks) # count task occurrences\n",
    "        cpu_slots       = []                         # a sequence depicting which task runs when\n",
    "        runq            = []                         # a run queue,  a priority queue\n",
    "        waitq = collections.deque([])                # a wait queue, a simple queue\n",
    "\n",
    "        # push all tasks in a run que\n",
    "        for name, count in task_collection.items():\n",
    "            heapq.heappush(runq, Task(name, count))  # higher the instances, higher the priority\n",
    "\n",
    "        idle_task = Task(\"idle\", 0) # an idle task\n",
    "        time = 0                    # clock\n",
    "        while runq or waitq:        # if at least one of the queue has some tasks to run\n",
    "            \n",
    "            if waitq and ( time - waitq[0].time ) > n:  # if wait queue has task whose cooling period has come\n",
    "                heapq.heappush(runq,waitq.popleft())    # put that task in run queue\n",
    "\n",
    "            if runq:     # schdule highest priority task, if one is ready\n",
    "                task = heapq.heappop(runq)\n",
    "                task.schedule(time)  # consume one instance\n",
    "            else:       # no task is ready, so schedule idle task\n",
    "                task = idle_task\n",
    "\n",
    "            cpu_slots.append(task.name) # task scheduled on CPU\n",
    "            if task is not idle_task and task.count != 0:\n",
    "                waitq.append(task)      # if task is not idle task and has at least some instances to run\n",
    "            time += 1\n",
    "\n",
    "        return len(cpu_slots)   # cpu slots will also print task schedule"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastInterval(self, tasks: 'List[str]', n: 'int') -> 'int':\n",
    "        M = 0\n",
    "        numM = 0\n",
    "        count = [0]*26\n",
    "        for i in tasks:\n",
    "            tmp = ord(i[0])\n",
    "            #ord('A')\n",
    "            count[tmp -ord('A')] += 1\n",
    "            if M == count[tmp-ord('A')]:\n",
    "                numM += 1\n",
    "            elif M < count[tmp-ord('A')]:\n",
    "                numM = 1\n",
    "                M = count[tmp-ord('A')]\n",
    "                    \n",
    "        return max(0,-((len(tasks)-M*numM)-(M-1)*(n-(numM-1)))) + len(tasks)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastInterval(self, tasks: List[str], n: int) -> int:\n",
    "        cnt = [0 for _ in range(26)]\n",
    "        for task in tasks:\n",
    "            cnt[ord(task)-ord('A')]+=1\n",
    "            \n",
    "        cnt.sort(reverse=True)\n",
    "        \n",
    "        k = cnt[0]\n",
    "        i=0\n",
    "        while cnt[i]==k:\n",
    "            i+=1\n",
    "        return max(len(tasks),(k-1)*(n+1)+i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastInterval(self, tasks: List[str], n: int) -> int:\n",
    "        count = [0] * 26\n",
    "        for tchr in tasks:\n",
    "            count[ord(tchr) - ord('A')] += 1\n",
    "        count.sort(reverse=True)\n",
    "        max_val = count[0] - 1\n",
    "        res = max_val * n\n",
    "        for i in range(1,len(count)):\n",
    "            res -= min(max_val,count[i])\n",
    "        return len(tasks) + res if res > 0 else len(tasks)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heappush, heapify, heappop\n",
    "\n",
    "class Solution:\n",
    "    def leastInterval(self, tasks: List[str], n: int) -> int:\n",
    "        if not tasks:\n",
    "            return\n",
    "\n",
    "        d = {}\n",
    "        for c in tasks:\n",
    "            d[c] = d.get(c, 0) + 1\n",
    "\n",
    "        heap = [[-i, c] for c, i in d.items()]\n",
    "        heapify(heap)\n",
    "\n",
    "        times = 0\n",
    "\n",
    "        while heap:\n",
    "            count=min(n+1, len(heap))\n",
    "            l=[]\n",
    "            for _ in range(count):\n",
    "                node=heappop(heap)\n",
    "                if node[0]!=-1:\n",
    "                    node[0]+=1\n",
    "                    l.append(node)\n",
    "            for node in l:\n",
    "                heappush(heap, node)\n",
    "            if heap:\n",
    "                times+=n+1\n",
    "            else:\n",
    "                times+=count\n",
    "        return times\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def leastInterval(self, tasks, n):\n",
    "        \"\"\"\n",
    "        :type tasks: List[str]\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        length = len(tasks)\n",
    "        if length <= 1:\n",
    "            return length\n",
    "        \n",
    "        # 用于记录每个任务出现的次数\n",
    "        task_map = dict()\n",
    "        for task in tasks:\n",
    "            task_map[task] = task_map.get(task, 0) + 1\n",
    "        # 按任务出现的次数从大到小排序\n",
    "        task_sort = sorted(task_map.items(), key=lambda x: x[1], reverse=True)\n",
    "        \n",
    "        # 出现最多次任务的次数\n",
    "        max_task_count = task_sort[0][1]\n",
    "        # 至少需要的最短时间\n",
    "        res = (max_task_count - 1) * (n + 1)\n",
    "        \n",
    "        for sort in task_sort:\n",
    "            if sort[1] == max_task_count:\n",
    "                res += 1\n",
    "        \n",
    "        # 如果结果比任务数量少，则返回总任务数\n",
    "        return res if res >= length else length\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastInterval(self, tasks: List[str], n: int) -> int:\n",
    "        num2cnt = dict()\n",
    "        for task in tasks:\n",
    "            num2cnt[task] = num2cnt.get(task, 0) + 1\n",
    "        num2cnt = sorted(num2cnt.items(), key=lambda key: -key[1])\n",
    "        if n == 0:\n",
    "            res = len(tasks)\n",
    "        elif num2cnt[0][1] > len(tasks) // 2:\n",
    "            res = (num2cnt[0][1] - 1) * (n + 1) + 1\n",
    "        else:\n",
    "            res = (num2cnt[0][1] - 1) * (n + 1) + 1\n",
    "            for _, val in num2cnt[1:]:\n",
    "                if val == num2cnt[0][1]:\n",
    "                    res += 1\n",
    "                else:\n",
    "                    break\n",
    "        return max(len(tasks), res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastInterval(self, tasks: List[str], n: int) -> int:\n",
    "        freq = [0 for _ in range(26)]\n",
    "        for c in tasks:\n",
    "            freq[ord(c) - ord('A')] += 1 \n",
    "        freq.sort(key = lambda x : -x)\n",
    "        cnt = 0\n",
    "        while cnt < len(freq) and freq[cnt] == freq[0]:\n",
    "            cnt += 1\n",
    "        return max(len(tasks),cnt + (n + 1) * (freq[0] - 1))\n",
    "\n",
    "        # freq = collections.Counter(tasks)\n",
    "        # maxExec = max(freq.values())# 最多的执行次数\n",
    "        # maxCount = sum(1 for v in freq.values() if v == maxExec)# 具有最多执行次数的任务数量\n",
    "        # return max((maxExec - 1) * (n + 1) + maxCount,len(tasks))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastInterval(self, tasks: List[str], n: int) -> int:\n",
    "        length = len(tasks)\n",
    "        hash_map = {}\n",
    "        # 哈希表\n",
    "        for i in range(length):\n",
    "            task = tasks[i]\n",
    "            hash_map[task] = hash_map.get(task, 0) + 1\n",
    "        # 降序排序\n",
    "        task_sort = sorted(hash_map.items(), key = lambda x: x[1], reverse = True)\n",
    "        task_max_num = task_sort[0][1]\n",
    "        min_time = (task_max_num - 1) * (n + 1)\n",
    "        for item in task_sort:\n",
    "            if item[1] == task_max_num:\n",
    "                min_time += 1\n",
    "        return min_time if min_time > length else length\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastInterval(self, tasks: List[str], n: int) -> int:\n",
    "        if n == 0:\n",
    "            return len(tasks)\n",
    "        counter = {}\n",
    "        for t in tasks:\n",
    "            if t in counter:\n",
    "                counter[t] += 1\n",
    "            else:\n",
    "                counter[t] = 1\n",
    "\n",
    "        timer = {}\n",
    "        for k in counter:\n",
    "            timer[k] = True\n",
    "        res = len(tasks)\n",
    "        seq = []\n",
    "        while res > 0:\n",
    "            best_candidate_num = 0\n",
    "            best_candidate = ''\n",
    "            for key in counter:\n",
    "                if timer[key]:\n",
    "                    if counter[key] > best_candidate_num:\n",
    "                        best_candidate = key\n",
    "                        best_candidate_num =counter[key]\n",
    "            if len(seq) >= n:\n",
    "                if seq[-n] != '':\n",
    "                    timer[seq[-n]] = True\n",
    "            seq.append(best_candidate)\n",
    "            if best_candidate in timer:\n",
    "                timer[best_candidate] = False\n",
    "\n",
    "\n",
    "            if best_candidate in counter:\n",
    "                res -= 1\n",
    "                if counter[best_candidate] == 1:\n",
    "                    del counter[best_candidate]\n",
    "                else:\n",
    "                    counter[best_candidate] -= 1\n",
    "        return len(seq)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import PriorityQueue, Queue\n",
    "class Solution:\n",
    "    def leastInterval(self, tasks: List[str], n: int) -> int:\n",
    "        class t:\n",
    "            def __init__(self, task, ct):\n",
    "                self.task = task\n",
    "                self.ct = ct\n",
    "            \n",
    "            def __lt__(self, other):\n",
    "                return self.ct > other.ct\n",
    "\n",
    "        d = {}\n",
    "        for task in tasks:\n",
    "            if task in d:\n",
    "                d[task] += 1\n",
    "            else:\n",
    "                d[task] = 1\n",
    "\n",
    "        # put in heap\n",
    "        q = PriorityQueue()\n",
    "        for task in d:\n",
    "            q.put(t(task, d[task]))\n",
    "        \n",
    "        # put\n",
    "        times, time2obj = Queue(), {}\n",
    "        ct_time = 0\n",
    "        while not q.empty():\n",
    "            if ct_time in time2obj:\n",
    "                q.put(time2obj[ct_time])\n",
    "                times.get()\n",
    "\n",
    "            ele = q.get()\n",
    "            if ele.ct > 1:\n",
    "                ele.ct -= 1\n",
    "                time2obj[ct_time+n+1] = ele\n",
    "                times.put(ct_time+n+1)\n",
    "            ct_time += 1\n",
    "\n",
    "        while not times.empty():\n",
    "            time = times.get()\n",
    "            ct_time = max(ct_time, time + (time2obj[time].ct-1)*(n+1)+1)\n",
    "\n",
    "        return ct_time\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastInterval(self, tasks: List[str], n: int) -> int:\n",
    "\n",
    "        ready = []\n",
    "        c = {}\n",
    "        for task in tasks:\n",
    "            if task not in c:\n",
    "                c[task] = 0\n",
    "            c[task] -= 1\n",
    "        for task, num in c.items():\n",
    "            heapq.heappush(ready,[num,task])\n",
    "        ans = 0\n",
    "        wait = collections.deque()\n",
    "        total = len(tasks)\n",
    "        seq = []\n",
    "        while total:\n",
    "            ans += 1\n",
    "            if len(wait) > n:\n",
    "                p = wait.popleft()\n",
    "                if p:\n",
    "                    heapq.heappush(ready,p)\n",
    "            # print(ready,wait)\n",
    "            if not ready:\n",
    "                wait.append([])\n",
    "                seq.append('idle')\n",
    "            else:\n",
    "                num,task = heapq.heappop(ready)\n",
    "                total -= 1\n",
    "                seq.append(task)\n",
    "                if num+1 < 0:\n",
    "                    wait.append([num+1,task])\n",
    "                else:\n",
    "                    wait.append([])\n",
    "            \n",
    "            \n",
    "            # print(seq)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastInterval(self, tasks: List[str], n: int) -> int:\n",
    "        ans=0\n",
    "        dic=Counter(tasks)\n",
    "        queue=[(-x[1],x[0]) for x in dic.items()]\n",
    "        heapq.heapify(queue)\n",
    "        res=[]\n",
    "        while queue:\n",
    "            count=n+1\n",
    "            while count:\n",
    "                if queue:\n",
    "                    temp=heapq.heappop(queue)\n",
    "                    res.append(temp[1])\n",
    "                    dic[temp[1]]-=1\n",
    "                else:\n",
    "                    res.append(' ')\n",
    "                count-=1\n",
    "\n",
    "            count=1\n",
    "            while count<=n+1:\n",
    "                temp=res[-count]\n",
    "                if temp!=' ' and dic[temp]!=0:\n",
    "                    heapq.heappush(queue,(-dic[temp],temp))\n",
    "                count+=1\n",
    "        res=\"\".join(res).strip()\n",
    "        ans=len(res)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastInterval(self, tasks: List[str], n: int) -> int:\n",
    "        if n==0:\n",
    "            return len(tasks)\n",
    "\n",
    "        tdic={}\n",
    "        for t in tasks:\n",
    "            tdic[t]=tdic.get(t,0)+1\n",
    "\n",
    "        kdic=sorted(tdic.items(),key=lambda x:x[1],reverse=True)\n",
    "        kdic=[x[0] for x in kdic]\n",
    "\n",
    "        q=[]\n",
    "        t=0     \n",
    "        while tdic:\n",
    "            # 寻找下一个任务\n",
    "            flg=False\n",
    "            for i in range(len(kdic)):\n",
    "                for j in range(1,n+1):\n",
    "                    if t-j<0:\n",
    "                        flg=True\n",
    "                        break\n",
    "                    if kdic[i]==q[t-j]:\n",
    "                        break\n",
    "                    elif j==n:\n",
    "                        flg=True\n",
    "\n",
    "                if flg:\n",
    "                    q.append(kdic[i])\n",
    "                    tdic[kdic[i]]-=1\n",
    "                    t+=1\n",
    "                    break\n",
    "\n",
    "            if not flg:\n",
    "                # 寻找下一个等待时间最短的任务\n",
    "                i=t if n>t else n\n",
    "                while i>0:\n",
    "                    if q[t-i] in tdic:\n",
    "                        q+=['wait...' for x in range(n-i+1)]\n",
    "                        q.append(q[t-i])\n",
    "                        tdic[q[t-i]]-=1\n",
    "                        t+=2+n-i\n",
    "                        flg=True\n",
    "                        break\n",
    "                    i-=1\n",
    "            \n",
    "            if flg:\n",
    "                if tdic[q[-1]]==0:\n",
    "                    del tdic[q[-1]]\n",
    "                    kdic.pop(kdic.index(q[-1]))\n",
    "                if t%n==0:\n",
    "                    kdic=sorted(tdic.items(),key=lambda x:x[1],reverse=True)\n",
    "                    kdic=[x[0] for x in kdic]\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        # print(q)\n",
    "        return t\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def leastInterval(self, tasks: List[str], n: int) -> int:\n",
    "        c = Counter(tasks)\n",
    "        pq = []\n",
    "        for key in c:\n",
    "            heapq.heappush(pq, (-c[key], key))\n",
    "        task_types = len(c)\n",
    "        i = 0\n",
    "        d = {}\n",
    "        while task_types > 0:\n",
    "            i += 1\n",
    "            if i in d:\n",
    "                heapq.heappush(pq, d[i])\n",
    "            if len(pq) <= 0:\n",
    "                continue\n",
    "            v, k = heapq.heappop(pq)\n",
    "            v += 1\n",
    "            if v < 0:\n",
    "                d[i + n + 1] = (v, k)\n",
    "            else:\n",
    "                task_types -= 1\n",
    "        return i\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastInterval(self, tasks: List[str], n: int) -> int:\n",
    "        q = collections.deque()\n",
    "        dict_tasks = dict(sorted(collections.Counter(tasks).items(), key=lambda x:x[1], reverse=True))\n",
    "        length = len(tasks)\n",
    "        while length > 0:\n",
    "            cnt = 0\n",
    "            dict_tasks = dict(sorted(dict_tasks.items(), key=lambda x:x[1], reverse=True))\n",
    "            for key in dict_tasks.keys():\n",
    "                print(key, cnt, length)\n",
    "                if dict_tasks[key] == 0:\n",
    "                    continue\n",
    "                dict_tasks[key] -= 1\n",
    "                q.append(key)\n",
    "                cnt += 1\n",
    "                length -= 1\n",
    "                if cnt > n:\n",
    "                    break\n",
    "            if length == 0:\n",
    "                break\n",
    "            while cnt <= n:\n",
    "                q.append(0)\n",
    "                cnt += 1\n",
    "        print(q)\n",
    "        return len(q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastInterval(self, tasks: List[str], n: int) -> int:\n",
    "        tasklist = dict()\n",
    "        for task in tasks:\n",
    "            if task not in tasklist:\n",
    "                tasklist[task] = 1\n",
    "            else:\n",
    "                tasklist[task] += 1\n",
    "        countlist = list(tasklist.values())\n",
    "        tasklist = list(tasklist.keys())\n",
    "        \n",
    "        gap = [0] * len(tasklist)\n",
    "        out = 0\n",
    "        while len(tasks) > 0:\n",
    "            maxnum = 0\n",
    "            maxidx = -1\n",
    "            for idx in range(len(countlist)):\n",
    "                if gap[idx] > 0:\n",
    "                    gap[idx] -= 1\n",
    "                if countlist[idx] > maxnum and gap[idx] == 0:\n",
    "                    maxnum = countlist[idx]\n",
    "                    maxidx = idx\n",
    "            if maxidx >= 0:\n",
    "                countlist[maxidx] -= 1\n",
    "                tasks.remove( tasklist[maxidx] )\n",
    "                gap[maxidx] = n+1\n",
    "            out += 1\n",
    "\n",
    "        return out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastInterval(self, tasks: List[str], n: int) -> int:\n",
    "        tasklist = dict()\n",
    "        for task in tasks:\n",
    "            if task not in tasklist:\n",
    "                tasklist[task] = 1\n",
    "            else:\n",
    "                tasklist[task] += 1\n",
    "        countlist = list(tasklist.values())\n",
    "        tasklist = list(tasklist.keys())\n",
    "        \n",
    "        gap = [0] * len(tasklist)\n",
    "        out = 0\n",
    "        while len(tasks) > 0:\n",
    "            maxnum = 0\n",
    "            maxidx = -1\n",
    "            for idx in range(len(countlist)):\n",
    "                if gap[idx] > 0:\n",
    "                    gap[idx] -= 1\n",
    "                if countlist[idx] > maxnum and gap[idx] == 0:\n",
    "                    maxnum = countlist[idx]\n",
    "                    maxidx = idx\n",
    "            if maxidx >= 0:\n",
    "                countlist[maxidx] -= 1\n",
    "                tasks.remove( tasklist[maxidx] )\n",
    "                gap[maxidx] = n+1\n",
    "            out += 1\n",
    "\n",
    "        return out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastInterval(self, tasks: List[str], n: int) -> int:\n",
    "        if n == 0:\n",
    "            return len(tasks)\n",
    "\n",
    "        taskDict = {}\n",
    "        for key in set(tasks):\n",
    "            taskDict[key] = tasks.count(key)\n",
    "       \n",
    "        result = 0\n",
    "        while len(tasks) > 0:\n",
    "            selectTask = []\n",
    "            selectFalg = False\n",
    "\n",
    "            # 排序\n",
    "            sortTask = sorted(taskDict.items(), key=lambda x:x[1], reverse=True)\n",
    "            for key, count in sortTask:\n",
    "                if key not in selectTask and count > 0:\n",
    "                    selectTask.append(key)\n",
    "                    taskDict[key] -= 1\n",
    "                if len(selectTask) > n:\n",
    "                    selectFalg = True\n",
    "                    break\n",
    "\n",
    "            # 删除已选择的任务\n",
    "            for task in selectTask:\n",
    "                tasks.remove(task)\n",
    "            result += len(selectTask)\n",
    "            print(selectTask)\n",
    "    \n",
    "            if not selectFalg and len(tasks) > 0:\n",
    "                # 未满\n",
    "                result += (n+1-len(selectTask))\n",
    "             \n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastInterval(self, tasks: List[str], n: int) -> int:\n",
    "        m = len(tasks)\n",
    "        if m == 1:\n",
    "            return m\n",
    "        dic = {}\n",
    "        for task in tasks:\n",
    "            if task not in dic:\n",
    "                dic[task] = 1\n",
    "            else:\n",
    "                dic[task] +=1\n",
    "        li = dic.values()\n",
    "        li = sorted(li,reverse = True)\n",
    "        min_time = (li[0]-1)*(n+1)\n",
    "        ct = 1\n",
    "        for i in range(1,len(li)):\n",
    "            if li[i] !=li[0]:\n",
    "                break\n",
    "            ct +=1\n",
    "        min_time += ct\n",
    "        return m if min_time<m else min_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastInterval(self, tasks: List[str], n: int) -> int:\n",
    "        values = collections.Counter(tasks).values()\n",
    "        maxValue = max(values)\n",
    "        maxCount = sum(1 for v in values if v == maxValue)\n",
    "        return max((maxValue-1)*(n+1) + maxCount,len(tasks))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastInterval(self, tasks: List[str], n: int) -> int:\n",
    "        freq = collections.Counter(tasks)\n",
    "\n",
    "        # 最多的执行次数\n",
    "        maxExec = max(freq.values())\n",
    "        # 具有最多执行次数的任务数量\n",
    "        maxCount = sum(1 for v in freq.values() if v == maxExec)\n",
    "\n",
    "        return max((maxExec - 1) * (n + 1) + maxCount, len(tasks))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections \n",
    "class Solution:\n",
    "    def leastInterval(self, tasks: List[str], n: int) -> int:\n",
    "        count = collections.Counter(tasks)\n",
    "        maxNum = max(count.values())\n",
    "        maxCount = sum([1 for x in count.values() if x == maxNum])\n",
    "        return max(len(tasks),(maxNum-1)*(n+1)+maxCount)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastInterval(self, tasks: List[str], n: int) -> int:\n",
    "        mp = Counter(tasks)\n",
    "        max_exec = max(mp.values())\n",
    "        max_cnt = sum(1 for v in mp.values() if v == max_exec)\n",
    "        return max((max_exec - 1) * (n + 1) + max_cnt, len(tasks))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastInterval(self, tasks: List[str], n: int) -> int:\n",
    "        count=list(collections.Counter(tasks).values())\n",
    "        maxCount=max(count)\n",
    "        extMaxCount=count.count(maxCount)\n",
    "        return max((maxCount-1)*(n+1)+extMaxCount,len(tasks))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leastInterval(self, tasks: List[str], n: int) -> int:\n",
    "        # freq = collections.Counter(tasks)\n",
    "\n",
    "        # # 最多的执行次数\n",
    "        # maxExec = max(freq.values())\n",
    "        # # 具有最多执行次数的任务数量\n",
    "        # maxCount = sum(1 for v in freq.values() if v == maxExec)\n",
    "\n",
    "        # return max((maxExec - 1) * (n + 1) + maxCount, len(tasks))\n",
    "        if n == 0: return len(tasks)\n",
    "        dict_ = defaultdict(int)\n",
    "        for i in range(len(tasks)):\n",
    "            dict_[tasks[i]] += 1\n",
    "        sortdict = sorted(dict_.values(),reverse=True)\n",
    "        count = sortdict[0] + (sortdict[0] - 1) * n\n",
    "        for i in range(1,len(sortdict)):\n",
    "            if sortdict[0] != sortdict[i]:\n",
    "                break\n",
    "            count += 1\n",
    "        return max(sum(sortdict),count)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
